package datastructure.graph.有向图;

import java.util.Stack;

/**
 * 单点有向路径，查找从s到给定目的顶点v是否存在一条有向路径
 * @author MaoLin Wang
 * @date 2020/2/2211:47
 */
public class DepthFirstDirectedPaths {
    private final int s;
    private int[] edgeTo;
    private boolean[] marked;

    public DepthFirstDirectedPaths(Digraph digraph, int s) {
        this.s = s;
        marked=new boolean[digraph.V()];
        edgeTo=new int[digraph.V()];
        validate(s);
        dfs(digraph,s);
    }

    private void dfs(Digraph digraph, int v) {
        marked[v]=true;
        for (int w:digraph.adj(v)){
            if (!marked[w]){
                edgeTo[w]=v;
                dfs(digraph,w);
            }
        }
    }

    public boolean hasPathTo(int v){
        return marked[v];
    }

    public Iterable<Integer> pathTo(int v){
        validate(v);
        if (!hasPathTo(v)){
            return null;
        }

        Stack<Integer>stack=new Stack<>();
        for (int i = v; i !=s ; i=edgeTo[i]) {
            stack.push(i);
        }
        stack.push(s);

        return stack;
    }
    private void validate(int v) {

        int V = marked.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }
}
